翻訳と辞書 Words near each other ・ Shoqarij-e Sofla ・ Shoqata e Guidave dhe Skoutëve në Shqipëri ・ Shoqata Mbarëkombëtare e të Përndjekurve Politikë Shqiptare ・ Shoqata Çameria ・ ShoqBox ・ Shor ・ Shor (film) ・ Shor in the City ・ Shor language ・ Shor Macha ・ Shor Shor ・ Shor Shor, Razavi Khorasan ・ Shor Shoreh ・ Shor Shoreh, Dorud ・ Shor Shoreh, Markazi ・ Shor's algorithm ・ Shorabak District ・ Shorabil Lake ・ SHORAN ・ Shorang Rang ・ Shoranur ・ Shoranur Junction railway station ・ Shoranur–Cochin Harbour section ・ Shoranur–Mangalore section ・ Shorapani ・ Shorapur ・ Shorashim ・ Shorashim (disambiguation) ・ Shorashim (organization) ・ Shorb ol Ayn Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Shor's algorithm ： ウィキペディア英語版 Shor's algorithm Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization formulated in 1994. Informally it solves the following problem: given an integer ''N'', find its prime factors. On a quantum computer, to factor an integer ''N'', Shor's algorithm runs in polynomial time (the time taken is polynomial in log ''N'', which is the size of the input).〔See also Pseudo-polynomial time.〕 Specifically it takes quantum gates of order ) using fast multiplication, demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is thus in the complexity class BQP. This is substantially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time — about .〔(【引用サイトリンク】title=Number Field Sieve )〕 The efficiency of Shor's algorithm is due to the efficiency of the quantum Fourier transform, and modular exponentiation by repeated squarings. If a quantum computer with a sufficient number of qubits could operate without succumbing to noise and other quantum decoherence phenomena, Shor's algorithm could be used to break public-key cryptography schemes such as the widely used RSA scheme. RSA is based on the assumption that factoring large numbers is computationally intractable. So far as is known, this assumption is valid for classical (non-quantum) computers; no classical algorithm is known that can factor in polynomial time. However, Shor's algorithm shows that factoring is efficient on an ideal quantum computer, so it may be feasible to defeat RSA by constructing a large quantum computer. It was also a powerful motivator for the design and construction of quantum computers and for the study of new quantum computer algorithms. It has also facilitated research on new cryptosystems that are secure from quantum computers, collectively called post-quantum cryptography. In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 × 5, using an NMR implementation of a quantum computer with 7 qubits. After IBM's implementation, two independent groups, one at the University of Science and Technology of China, and the other one at the University of Queensland, have implemented Shor's algorithm using photonic qubits, emphasizing that multi-qubit entanglement was observed when running the Shor's algorithm circuits. In 2012, the factorization of 15 was repeated. Also in 2012, the factorization of 21 was achieved, setting the record for the largest number factored with a quantum computer. In April 2012, the factorization of 143 was achieved, although this used adiabatic quantum computation rather than Shor's algorithm. It was discovered in November 2014 that this adiabatic quantum computation in 2012 had in fact also factored larger numbers, the largest being 56153, which is currently the record for the largest integer factored on a quantum device. == Procedure == The problem we are trying to solve is: given an odd composite number $N$, find an integer $d$, strictly between $1$ and $N$, that divides $N$. We are interested in odd values of $N$ because any even value of $N$ trivially has the number $2$ as a prime factor. We can use a primality testing algorithm to make sure that $N$ is indeed composite. Moreover, for the algorithm to work, we need $N$ not to be the power of a prime. This can be tested by checking that $\backslash sqrt()$ is not an integer, for all $k\; \backslash le\; \backslash log\_(N)$. Since $N$ is not a power of a prime, it is the product of two coprime numbers greater than $1$. As a consequence of the Chinese remainder theorem, the number $1$ has at least four distinct square roots modulo $N$, two of them being $1$ and $-1$. The aim of the algorithm is to find a square root $b$ of one other factor; such a $b$ will lead to a factorization of $N$, as in other factoring algorithms like the quadratic sieve. In turn, finding such a $b$ is reduced to finding an element $a$ of even period with a certain additional property (as explained below, it is required that the condition of Step 6 of the classical part does not hold). The quantum algorithm is used for finding the period of randomly chosen elements $a$, as order-finding is a hard problem on a classical computer. Shor's algorithm consists of two parts: # A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding. # A quantum algorithm to solve the order-finding problem. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Shor's algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.